/* WUGraph.java */

package graph;

import java.util.Hashtable;
import list.*;

/**
 * The WUGraph class represents a weighted, undirected graph.  Self-edges are
 * permitted.
 */

public class WUGraph {

  private Hashtable<Object, ListNode> vertexHash;
  private Hashtable<VertexPair, ListNode> edgeHash;
  private DList vertexDList;
  private int edges = 0;

  
  /**
   * WUGraph() constructs a graph having no vertices or edges.
   *
   * Running time:  O(1).
   */
  public WUGraph() {
	  vertexHash = new Hashtable<Object, ListNode>();
	  edgeHash = new Hashtable<VertexPair, ListNode>();
	  vertexDList = new DList();
  }

  /**
   * vertexCount() returns the number of vertices in the graph.
   *
   * Running time:  O(1).
   */
  public int vertexCount() {
	  return vertexDList.length();
  }

  /**
   * edgeCount() returns the number of edges in the graph.
   *
   * Running time:  O(1).
   */
  public int edgeCount() {
	  return edges;
  }

  /**
   * getVertices() returns an array containing all the objects that serve
   * as vertices of the graph.  The array's length is exactly equal to the
   * number of vertices.  If the graph has no vertices, the array has length
   * zero.
   *
   * (NOTE:  Do not return any internal data structure you use to represent
   * vertices!  Return only the same objects that were provided by the
   * calling application in calls to addVertex().)
   *
   * Running time:  O(|V|).
   */
  public Object[] getVertices(){
	  Object[] result = new Object[vertexCount()];
	  DListNode temp = (DListNode) vertexDList.front();
	  for (int i = 0; i < vertexDList.length(); i++) {
		  try {
			  result[i] = ((Vertex) temp.VertexDListNode()).getVertex();
			  temp = (DListNode) temp.next();
		  }catch (InvalidNodeException e) {
			  System.out.println("error: empty vertexDList");
		  }
	  }
	  return result;
  }

  /**
   * addVertex() adds a vertex (with no incident edges) to the graph.  The
   * vertex's "name" is the object provided as the parameter "vertex".
   * If this object is already a vertex of the graph, the graph is unchanged.
   *
   * Running time:  O(1).
   */
  public void addVertex(Object vertex) {
	  if (!isVertex(vertex)) {
		  vertexDList.insertFront(new Vertex(vertex, vertexDList));
		  vertexHash.put(vertex, vertexDList.front());
	  }
  }

  /**
   * removeVertex() removes a vertex from the graph.  All edges incident on the
   * deleted vertex are removed as well.  If the parameter "vertex" does not
   * represent a vertex of the graph, the graph is unchanged.
   *
   * Running time:  O(d), where d is the degree of "vertex".
   */
  public void removeVertex(Object vertex){
	  if (isVertex(vertex)) {
		  try {
			  ListNode vert = vertexHash.get(vertex);
			  EdgeList eList = ((DListNode) vert).VertexDListNode().getEList();
			  edges -=  eList.length();
			  eList.destroy(edgeHash);
			  vert.remove();
		  } catch (InvalidNodeException e) {
			  System.out.println("Error: removeVertex() on invalidnode");
		  }
		  vertexHash.remove(vertex);
	  }

  }
  
  /**
   * isVertex() returns true if the parameter "vertex" represents a vertex of
   * the graph.
   *
   * Running time:  O(1).
   */
  public boolean isVertex(Object vertex){
	  return vertexHash.containsKey(vertex);
  }

  /**
   * degree() returns the degree of a vertex.  Self-edges add only one to the
   * degree of a vertex.  If the parameter "vertex" doesn't represent a vertex
   * of the graph, zero is returned.
   *
   * Running time:  O(1).
   */
  public int degree(Object vertex){
	  if (!isVertex(vertex)) {
		  return 0;
	  } else
		  return  ((DListNode) vertexHash.get(vertex)).VertexDListNode().getEList().length();  
  }

  /**
   * getNeighbors() returns a new Neighbors object referencing two arrays.  The
   * Neighbors.neighborList array contains each object that is connected to the
   * input object by an edge.  The Neighbors.weightList array contains the
   * weights of the corresponding edges.  The length of both arrays is equal to
   * the number of edges incident on the input vertex.  If the vertex has
   * degree zero, or if the parameter "vertex" does not represent a vertex of
   * the graph, null is returned (instead of a Neighbors object).
   *
   * The returned Neighbors object, and the two arrays, are both newly created.
   * No previously existing Neighbors object or array is changed.
   *
   * (NOTE:  In the neighborList array, do not return any internal data
   * structure you use to represent vertices!  Return only the same objects
   * that were provided by the calling application in calls to addVertex().)
   *
   * Running time:  O(d), where d is the degree of "vertex".
   */
  public Neighbors getNeighbors(Object vertex){
	  if (degree(vertex) == 0 || !isVertex(vertex)) {
		  return null;
	  } else {
		  return ((DListNode) vertexHash.get(vertex)).VertexDListNode().getEList().getNeighbors(vertex);
	  }
  }

  /**
   * addEdge() adds an edge (u, v) to the graph.  If either of the parameters
   * u and v does not represent a vertex of the graph, the graph is unchanged.
   * The edge is assigned a weight of "weight".  If the edge is already
   * contained in the graph, the weight is updated to reflect the new value.
   * Self-edges (where u == v) are allowed.
   *
   * Running time:  O(1).
   */
  public void addEdge(Object u, Object v, int weight){
	  if (isEdge(u,v)) {
		  try {
			((Edge) ((ListNode) edgeHash.get(new VertexPair(u,v))).item()).setWeight(weight);
		} catch (InvalidNodeException e) {
			System.out.println("Error: addEdge invalid node");
		}
	  } else if (isVertex(u) && isVertex(v)) {
		  Edge e = new Edge(new VertexPair(u,v), weight);
		  DListNode unode = (DListNode) vertexHash.get(u);
		  DListNode vnode = (DListNode) vertexHash.get(v);
		  if (u != v) {
			  unode.VertexDListNode().getEList().insertFront(e);
		  }
		  vnode.VertexDListNode().getEList().insertFront(e);
		  EdgeListNode edgeListNode = (EdgeListNode) ((Vertex) unode.VertexDListNode()).getEList().front();
		  edgeListNode.setPartner((EdgeListNode) ((Vertex) vnode.VertexDListNode()).getEList().front());
		  edgeHash.put(new VertexPair(u,v), edgeListNode);
		  edges++;
	  }
	  
  }

  /**
   * removeEdge() removes an edge (u, v) from the graph.  If either of the
   * parameters u and v does not represent a vertex of the graph, the graph
   * is unchanged.  If (u, v) is not an edge of the graph, the graph is
   * unchanged.
   *
   * Running time:  O(1).
   */
  public void removeEdge(Object u, Object v){
	  if (isEdge(u,v)) {
		  try {
			  ((EdgeListNode) edgeHash.get(new VertexPair(u,v))).remove();
		  } catch (InvalidNodeException e) {
			  System.out.println("Error: removeEdge on invalidnode");
		  }
		  edgeHash.remove(new VertexPair(u,v));
		  edges--;
	  }
  }

  /**
   * isEdge() returns true if (u, v) is an edge of the graph.  Returns false
   * if (u, v) is not an edge (including the case where either of the
   * parameters u and v does not represent a vertex of the graph).
   *
   * Running time:  O(1).
   */
  public boolean isEdge(Object u, Object v){
	  return edgeHash.containsKey(new VertexPair(u,v));
  }

  /**
   * weight() returns the weight of (u, v).  Returns zero if (u, v) is not
   * an edge (including the case where either of the parameters u and v does
   * not represent a vertex of the graph).
   *
   * (NOTE:  A well-behaved application should try to avoid calling this
   * method for an edge that is not in the graph, and should certainly not
   * treat the result as if it actually represents an edge with weight zero.
   * However, some sort of default response is necessary for missing edges,
   * so we return zero.  An exception would be more appropriate, but
   * also more annoying.)
   *
   * Running time:  O(1).
   */
  public int weight(Object u, Object v){
	  if (isEdge(u,v)) {
		  try {
			return ((Edge) ((ListNode) edgeHash.get(new VertexPair(u,v))).item()).weight();
		} catch (InvalidNodeException e) {
			e.printStackTrace();
		}
	  }
	  return 0;
  }
  
  
  public static void main(String[] args) {
	  WUGraph test1 = new WUGraph();
	  System.out.println("vertexCount is " + test1.vertexCount());
	  test1.addVertex(1);
	  System.out.println("getVertices: " + test1.getVertices()[0]);

	
  }

}
